package middle;

/**
 * 19. 删除链表的倒数第N个节点
 * 给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 *
 * 给定的 保证是有效的。
 */

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {this.val = val;}
}

public class RemoveNthFromEnd {
    // 一次遍历方法
    public ListNode solve(ListNode head, int n){
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode end = dummy;

        for (int i = 0; i < n; i++){
            end = end.next;
        }

        while(end.next != null){
            first = first.next;
            end = end.next;
        }



        first.next = first.next.next;
        return dummy.next;
    }

    /**
     * 双指针法 —— 严谨版本
     * 其实改题 已经说明给定的N是有效的，但是在面试的时候，面试官通常不会给出你n的范围。
     * 所以这个时候我们就需要考虑到一种异常的情况，即给定的n比我们的链表长度要大
     * */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummyNode = new ListNode(0);
            dummyNode.next = head;
            ListNode firstPoint = dummyNode;
            ListNode latterPoint = dummyNode;
            // 将第一个指针先走n步
            while(n-- != 0 && firstPoint != null){
                firstPoint = firstPoint.next;
            }
            if(n > 0){
                throw new IllegalArgumentException("Param n is illegal");
            }

            while(firstPoint != null){
                latterPoint = latterPoint.next;
            }
            latterPoint.next = latterPoint.next.next;
            return head;
        }
    }

}
